﻿namespace 字符串相似度
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string str1 = "abc";
            string str2 = "baf";

            int distance = CalculateLevenshteinDistance(str1, str2);
            double similarity = 100.0 * (str1.Length - distance) / str1.Length;

            Console.WriteLine($"The Levenshtein distance between '{str1}' and '{str2}' is {distance}.");
            Console.WriteLine($"The similarity score is {similarity}.");
        }
        /// <summary>
        /// Calculates the Levenshtein distance between two strings.
        /// </summary>
        /// <param name="s1">First string.</param>
        /// <param name="s2">Second string.</param>
        /// <returns>The Levenshtein distance.</returns>
        public static int CalculateLevenshteinDistance(string s1, string s2)
        {
            if (s1 == null) throw new ArgumentNullException(nameof(s1));
            if (s2 == null) throw new ArgumentNullException(nameof(s2));

            int[,] distance = new int[s1.Length + 1, s2.Length + 1];

            for (int i = 0; i <= s1.Length; distance[i, 0] = i++) { }
            for (int j = 0; j <= s2.Length; distance[0, j] = j++) { }

            for (int i = 1; i <= s1.Length; i++)
                for (int j = 1; j <= s2.Length; j++)
                    distance[i, j] = Minimum(
                        distance[i - 1, j] + 1,
                        distance[i, j - 1] + 1,
                        distance[i - 1, j - 1] + ((s1[i - 1] == s2[j - 1]) ? 0 : 1));

            return distance[s1.Length, s2.Length];
        }
        /// <summary>
        /// 取最小值
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <param name="c"></param>
        /// <returns></returns>
        private static int Minimum(int a, int b, int c)
        {
            return Math.Min(Math.Min(a, b), c);
        }
    }
}
